/**
 * @author Bill
 * @date 2021年7月18日 15点24分
 * @Description 线性表——顺序表实现 
 * @version 1.0
 * [√] 自动扩容
 * [√] 线程不安全
 */

#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define InitCapacity 2      // 初始容量为2
#define MaxCapacity 1000000 // 100万为上限

typedef int DataType;

typedef struct
{
    DataType *data; // 数据
    int len;        // 有效数据个数
    int capacity;   // 可容纳数据个数
} Seqlist;

Seqlist InitList();                         // 初始化操作，建立一个空的线性表L
Seqlist InitList(int capacity);             // 初始化操作，建立一个空的线性表L，并指定容量
void Destroy(Seqlist &L);                   // 销毁已存在的线性表L
void Clear(Seqlist &L);                     // 将线性表清空
void Insert(Seqlist &L, DataType e);        // 一般插入方法，无指定位置
void Insert(Seqlist &L, int i, DataType e); // 在线性表L中第i(i从1开始)个位置插入新元素e
DataType Delete(Seqlist &L, int i);         // 删除线性表L中第i(i从1开始)个位置元素，返回删除的元素
int IsEmpty(Seqlist L);                     // 若线性表为空，返回true(1)，否则false(0)
int Length(Seqlist L);                      // 返回线性表L的元素个数
int LocateElem(Seqlist L, DataType e);      // L中查找与给定e相等的元素，若成功则返回该元素在表中的序号，否则返回0
DataType GetElem(Seqlist L, int i);         // 将线性表L中的第i(i从1开始)个位置元素返回
void Print(Seqlist L);                      // 打印顺序表
void PrintDetail(Seqlist L);                // 打印顺序表(带详情)

/**
 * 初始化顺序表 初始化容量为默认长度
 * @return Seqlist
 */
Seqlist InitList()
{
    return InitList(InitCapacity);
}

/**
 * 初始化顺序表 传入容量参数
 * @param int capacity
 * @return Seqlist
 */
Seqlist InitList(int capacity)
{
    if (capacity > MaxCapacity)
    {
        printf("已经超出所能分配的最大容量，已分配最大容量: %d\n", MaxCapacity);
        capacity = MaxCapacity;
    }
    Seqlist L;
    L.data = (DataType *)malloc(capacity * sizeof(DataType));
    L.len = 0;
    L.capacity = InitCapacity;
    return L;
}

/**
 * 销毁表 主要销毁data上挂载的数组
 * @param Seqlist &L
 */
void Destroy(Seqlist &L)
{
    if (sizeof(L.data) > 0)
        free(L.data);
    L.capacity = -1;
    L.len = -1;
}

/**
 * 清空表 恢复到初始容量
 * @param Seqlist &L
 */
void Clear(Seqlist &L)
{
    free(L.data);
    L.len = 0;
    L.data = (DataType *)malloc(InitCapacity * sizeof(DataType));
    L.capacity = InitCapacity;
}

/**
 * 插入元素 默认插入到表末尾
 * @param Seqlist &L
 * @param DataType e
 */
void Insert(Seqlist &L, DataType e)
{
    int i = L.len + 1; /// 默认插入到末尾位置
    Insert(L, i, e);
}

/**
 * 插入到指定元素位置之前,位置序号从1开始
 * @param Seqlist &L
 * @param int i
 * @param DataType e
 */
void Insert(Seqlist &L, int i, DataType e)
{
    if (L.len >= L.capacity)
    {
        int newCapacity = L.capacity << 1; // 动态扩容为原容量一倍
        int *newData = (DataType *)malloc(newCapacity * sizeof(DataType));
        memcpy(newData, L.data, L.len * sizeof(DataType)); // 直接拷贝整块内存
        int *oldData = L.data;
        free(oldData);
        L.data = newData; // 挂载新的大容量的存储空间
        L.capacity = newCapacity;
    }
    L.len++;
    for (int j = L.len; j > i; j--)
    {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
}

/**
 * 删除指定位置的元素,位置序号从1开始
 * @param Seqlist &L
 * @param int i
 * @return DataType
 */
DataType Delete(Seqlist &L, int i)
{
    DataType delItem = -1;
    if (i > L.len)
    {
        printf("删除的元素位置超出列表有效长度，删除无效\n");
        return delItem;
    }
    L.len--;
    delItem = L.data[i - 1];
    for (int j = i - 1; j < L.len; j++)
    {
        L.data[j] = L.data[j + 1];
    }
    return delItem;
}

/**
 * 表是否为空
 * @param Seqlist L
 */
int IsEmpty(Seqlist L)
{
    return L.len == 0;
}

/**
 * 表的长度
 * @param Seqlist L
 */
int Length(Seqlist L)
{
    return L.len;
}

/**
 * 定位元素的位置
 * @param Seqlist L
 * @param DataType e
 */
int LocateElem(Seqlist L, DataType e)
{
    for (int i = 0; i < L.len; i++)
    {
        if (L.data[i] == e)
            return i + 1;
    }
    return -1;
}

/**
 * 通过元素位置获取元素
 * @param Seqlist L
 * @param int i 位置从1开始
 */
DataType GetElem(Seqlist L, int i)
{
    if (i >= L.len)
    {
        printf("获取的元素位置超出表的有效长度\n");
        return -1;
    }
    return L.data[i - 1];
}

/**
 * 打印顺序表
 * @param Seqlist L
 */
void Print(Seqlist L)
{
    printf("[ ");
    for (int i = 0; i < L.len; i++)
    {
        printf("%d ", L.data[i]);
    }
    printf("]\n");
}

/**
 * 打印顺序表 带详细信息
 * @param Seqlist L
 */
void PrintDetail(Seqlist L)
{
    printf("Seqlist = [ ");
    for (int i = 0; i < L.len; i++)
    {
        printf("%d ", L.data[i]);
    }
    printf("], len = %d, capacity = %d \n", L.len, L.capacity);
}

/**
 * 测试
 */
int main()
{
    Seqlist L = InitList();
    for (int i = 1; i < 10; i++)
    {
        Insert(L, i);
        PrintDetail(L);
    }

    Insert(L, 1, 10);
    PrintDetail(L);

    printf("9的位置是: %d\n", LocateElem(L, 9));
    printf("第2个元素是: %d\n", GetElem(L, 2));

    Clear(L);
    PrintDetail(L);

    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    Delete(L, 1);
    PrintDetail(L);

    Destroy(L);
    Print(L);
    PrintDetail(L);
    return 0;
}